class Solution {
public:

    bool isValid(int *storage, int x, int n)
    {
        // check column
    	int y=storage[x];
    	int i;
    	for(i=0; i<n; i++)
    	{
    		if(i!=x && storage[i]==y)
    			break;
    	}
    
    	if(i!=n)
    		return false;
    
    	//check diagonal  
    	for(i=0; i<n; i++)
    	{
    		if(i!=x &&  storage[i]!=0)
    		{
    			if(storage[i]-y==i-x || storage[i]-y==x-i)
    				break;
    		}
    	}
    	if(i!=n)
    		return false;
    	return true;
    
    }
    vector<vector<string> > solveNQueens(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int board_size = n;
        vector<vector<string> > *return_list = new vector<vector<string> >();
        vector<string> initialized_string;
        
            int *storage=new int[board_size];
	    string tmp=string(board_size, '.');
        
        	for(int i=0; i<board_size; i++)
            {
                storage[i]=0;
                initialized_string.push_back(tmp);
            }
        		
        
        	bool flag=false;
        
        	int k=0;
        	while(k>=0)
        	{
        		while(storage[k]<board_size)
        		{
        			storage[k]++;
        			if(isValid(storage,k,board_size))
        			{
        				if(k==board_size-1)
        				{
        					vector<string> each_solution=initialized_string;
                            for(int i=0; i<board_size; i++)
                                each_solution[i][storage[i]-1]='Q';
                                
                            return_list->push_back(each_solution);    			
        				}
        				else
        					++k;
        			}
        		}
        	//	if(flag)
        	//		break;
        		storage[k]=0;
        		--k;
        	}
            return *return_list;
    }
};